// start with one pass over the two trees that will mark
// for every node a pointer to its heaviest child.

#ifndef __TREE_H__
#define __TREE_H__

#include <iostream>
#include <vector> 
#include <fstream>
#include "Node.h"//node
#include <deque>

using namespace std; 

class Tree 
{
	int Size;			// Size of sub tree (0 = leave) without the root
	Node* data;			// Node data
	deque<Tree*> children;		//all of trees children		
	Tree* heavyChild;	// pointer to the heavy child

	 

public:
	Tree();
	Tree(Node* data1);
	~Tree();

	void AddLeftTree(Tree* T);
	void AddRightTree(Tree* T);

	int getSize() const {return Size;}
	int getChildrenCount() const {return children.size();}
	Node* getData() const {return data;};
	Tree* getLeft() const;
	Tree* getRight() const;
	Tree* getHeavy()const {return heavyChild;}
	Tree* getChild(int i) const {return children.at(i);}

	void ClearHeavyPath();	//mark the heavy field as false for the heavy path
	void FindHeavyPath();	//mark the heaviest nodes & fill HeavyPath[n] & TopLight[n]
	void SelectRightHeavyPath();//marks the rightmost path as heavy
	int Postorder();		//postorder traversal which updates the Size parameter
	void PostOrderUpdateGetTree(int treeIndex,bool tempCount=true);//this function is used to fill GetTree[treeIndex]


	void Save(string filename) const;
	void SaveRec(ofstream& myfile) const;

	


	static vector<Tree*> GetTree[2];//a mapping between the nodes indexes in the postorder
									//left to right and the roots of the trees(0 stands for an empty tree)
};

Tree* Load(string& filename);
Tree* LoadRec(string& line, bool init);
void ClearSpaces(string& line);
string ItoS(int num); //int to string

#endif //__TREE_H__